using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace FileMapper {
    /*
     * List of Extents
     *
     * No overlapping extents allowed. Ordered by extent offsets.
     * Used for 2 things:
     *  - Storing the location of fixed parts of a file
     *  - Storing a mapping from the original positions to the new positions
     * Null extents are allowed if and only if it is a mapping.
     */
    public class ExtentList: IList<Extent>, IEquatable<ExtentList> {
        #region Fields
        private IList<Extent> list = new List<Extent>();
        #endregion

        #region Properties
        #region Inherited Properties
        public int Count {
            get { return list.Count; }
        }

        public bool IsReadOnly {
            get { return list.IsReadOnly; }
        }

        public Extent this[int index] {
            get { return list[index]; }
            set { list[index] = value; }
        }
        #endregion

        public long Length {
            get { return this.Sum((ext) => ext.Size); }
        }
        #endregion

        #region Constructors
        public ExtentList() {}
        #endregion

        #region Methods
        #region Inherited Methods
        public override bool Equals(object obj) {
            var ext = obj as ExtentList;
            return ext != null && this.Equals(ext);
        }

        public bool Equals(ExtentList other) {
            if (this.Count != other.Count) {
                return false;
            }
            for (int i = 0; i < this.Count; ++i) {
                if (!this[i].Equals(other[i])) {
                    return false;
                }
            }
            return true;
        }

        public override int GetHashCode() {
            int result = base.GetHashCode();
            foreach (var ext in this) {
                result = (result << 3) | (result >> 29);
                result ^= ext.GetHashCode();
            }
            return result;
        }

        public override string ToString () {
            string s = "ExtentList {\n";
            foreach (var ext in this) {
                s += "    " + ext.ToString() + "\n";
            }
            return s + "}";
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return list.GetEnumerator();
        }

        IEnumerator<Extent> IEnumerable<Extent>.GetEnumerator() {
            return list.GetEnumerator();
        }

        public void Add(Extent item) {
            //Check(item);
            list.Add(item);
        }

        public void Clear() {
            list.Clear();
        }

        public bool Contains(Extent item) {
            return list.Contains(item);
        }

        public void CopyTo(Extent[] array, int arrayIndex) {
            list.CopyTo(array, arrayIndex);
        }

        public bool Remove(Extent item) {
            return list.Remove(item);
        }

        public int IndexOf(Extent item) {
            return list.IndexOf(item);
        }

        public void Insert(int index, Extent item) {
            //Check(item);
            list.Insert(index, item);
        }

        public void RemoveAt(int index) {
            list.RemoveAt(index);
        }
        #endregion

        protected void Check(Extent extent) {
            if (list.Any(ext => ext.Overlaps(extent))) {
                throw new ArgumentException("Overlapping extents");
            }
        }

        public bool Contains(long position) {
            return list.Any(ext => ext.Contains(position));
        }

        public long? GetLogicalPosition(long? physicalPosition) {
            if (physicalPosition == null) {
                return null;
            }
            long logPos = 0;
            foreach (var ext in this) {
                if ((long)(physicalPosition) < ext.Offset) {
                    return null;
                } else if ((long)(physicalPosition) < ext.End) {
                    return logPos + (long)(physicalPosition) - ext.Offset;
                }
                logPos += ext.Size;
            }
            return null;
        }

        public long? GetPhysicalPosition(long? logicalPosition) {
            if (logicalPosition == null) {
                return null;
            }
            long logPos = 0;
            foreach (var extent in this) {
                long relPos = (long)(logicalPosition) - logPos;
                if (relPos < extent.Size) {
                    return (long)(extent.Offset) + relPos;
                } else {
                    logPos += extent.Size;
                }
            }
            return null;
        }

        public ExtentList GetLogicalExtents(Extent physicalExtent) {
            var remainder = new Extent { Offset = physicalExtent.Offset, Size = physicalExtent.Size };
            long logPos = 0;
            var logExts = new ExtentList();
            var prev = new Extent { Offset = 0, Size = 0 };
            foreach (var ext in this) {
                long logExtSize = 0;
                if ((long)(remainder.Offset) < (long)(ext.Offset)) {
                    // Before current extent
                    logExtSize = Math.Min(remainder.Size, (long)(ext.Offset) - (long)(prev.End));
                    logExts.Add(new Extent { Offset = null, Size = logExtSize });
                    remainder.Offset += logExtSize;
                    remainder.Size   -= logExtSize;
                    if (remainder.Size == 0) {
                        return logExts;
                    }
                }
                if ((long)(remainder.Offset) < (long)(ext.End)) {
                    // Inside current extent
                    logExtSize = Math.Min(remainder.Size, (long)(ext.End) - (long)(remainder.Offset));
                    logExts.Add(new Extent {
                        Offset = logPos + (long)(remainder.Offset) - (long)(ext.Offset),
                        Size = logExtSize
                    });
                    remainder.Offset += logExtSize;
                    remainder.Size   -= logExtSize;
                    if (remainder.Size == 0) {
                        return logExts;
                    }
                }
                logPos += ext.Size;
                prev = ext;
            }
            // Requested physical extent is out of the fixed area
            logExts.Add(new Extent { Offset = null, Size = remainder.Size });
            return logExts;
        }

        public ExtentList GetPhysicalExtents(Extent logicalExtent) {
            if (logicalExtent.Offset == null) {
                return new ExtentList { new Extent { Offset = null, Size = logicalExtent.Size } };
            }
            var phyExts = new ExtentList();
            var remainder = new Extent { Offset = logicalExtent.Offset, Size = logicalExtent.Size };
            long logPos = 0;
            foreach (var ext in this) {
                long relPos = (long)(remainder.Offset) - logPos;
                if (relPos < ext.Size) {
                    // Logical extent begins here
                    long phyExtSize = Math.Min(remainder.Size, ext.Size - relPos);
                    phyExts.Add(new Extent { Offset = ext.Offset + relPos, Size = phyExtSize });
                    remainder.Offset += phyExtSize;
                    remainder.Size   -= phyExtSize;
                }
                if (remainder.Size == 0) {
                    return phyExts;
                }
                logPos += ext.Size;
            }
            phyExts.Add(new Extent { Offset = null, Size = remainder.Size });
            return phyExts;
        }

        public ExtentList GetPhysicalExtents(ExtentList logicalExtents) {
            var phyExts = new ExtentList();
            foreach (var ext in logicalExtents) {
                foreach (var phy in GetPhysicalExtents(ext)) {
                    phyExts.Add(phy);
                }
            }
            return phyExts;
        }

        public ExtentList Intersection(ExtentList extents) {
            var result = new ExtentList();
            // TODO O(n) algorithm
            foreach (var ext1 in this) {
                foreach (var ext2 in extents) {
                    if (ext1.Overlaps(ext2)) {
                        long begin = Math.Max((long)(ext1.Offset), (long)(ext2.Offset));
                        long end = Math.Min((long)(ext1.End), (long)(ext2.End));
                        result.Add(new Extent { Offset = begin, Size = end - begin });
                    }
                }
            }
            return result;
        }
        #endregion
    }
}
